class Solution {
public:
    const int MOD =1e6;
    int numsOfStrings(int n, int k) {
        //dp[i][j]代表长度为i的字符串能够分成j段的字符串数量
        //然后是状态转移方程
        vector<vector<int>> dp(n+1,vector<int>(k+1,0));
         // 初始化
        int m = min(k, n / 2);//分成k段，因为每一段至少需要2个字符串，那么如果m =k至少n = 2*k,如果n达不到呢？所以
        //需要设定m
        for (int i = 2; i <= n; ++i)
        { 
            dp[i][1] = 26;
        }//长度为i，但是连续段为1的字符串数量，连续段为1代表字符串中的字符是一样的
        for(int i = 4;i<=n;i++)
        {
            for(int j = 2;j<=m;j++)
            {
                //dp[i][j]如果这个字符串的最后一个字符和i-1字符是一样的，此时dp[i][j] = dp[i-1][j],这个字符直接和前一个字符可以组成
                //连续段，此时dp[i][j] = dp[i-1][j],如果最后一个字符和前一个字符不一样，此时需要前i-2个字符串组成j-1段，然后最后两个字符
                //可以是不一样的，此时两个字符组成25种不同的组合
                dp[i][j] = dp[i-1][j] +25*dp[i-2][j-1];
                dp[i][j]%=MOD;
            }
        }
        return dp[n][k];
    }
};